#include <iostream>
#include <set>
#include <map>
#include <string>
#include <typeinfo>
#include <algorithm>
using namespace std;
void testset()
{
    set<int> s;
    s.insert(3);
    s.insert(1);
    s.insert(4);
    s.insert(3);
    s.insert(7);
    // 排序 + 去重
    set<int>::iterator it = s.begin();
    while (it != s.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;
    set<int> copy(s);
    for (auto e : copy)
    {
        cout << e << " ";
    }
    cout << endl;
    set<int>::reverse_iterator rit = s.rbegin();
    while (rit != s.rend())
    {
        cout << *rit << " ";
        ++rit;
    }
    cout << endl;
    set<int>::const_iterator cit = s.cbegin();
    while (cit != s.cend())
    {
        cout << *cit << " ";
        ++cit;
    }
    cout << endl;
    set<int>::const_reverse_iterator crit = s.crbegin();
    while (crit != s.crend())
    {
        cout << *crit << " ";
        ++crit;
    }
    cout << endl;
}
void testset1()
{
    set<int> s;
    s.insert(3);
    s.insert(1);
    s.insert(4);
    s.insert(3);
    s.insert(7);
    cout << s.count(3) << endl;
    // set<int>::iterator pos = s.find(3);//O(logn)
    set<int>::iterator pos = find(s.begin(), s.end(), 3); // O(n)
    if (pos != s.end())
    {
        s.erase(pos);
    }
    auto n = s.erase(4);
    s.erase(50);
    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;
    cout << n << endl;
    cout << typeid(n).name() << endl;
}
void testmap()
{
    map<int, int> m;
    m.insert(pair<int, int>(1, 1));
    m.insert(pair<int, int>(3, 3));
    m.insert(pair<int, int>(2, 2));
    m.insert(make_pair(4, 4));
    map<int, int>::iterator it = m.begin();
    while (it != m.end())
    {
        cout << (*it).first << " : " << (*it).second << endl;
        cout << it->first << " : " << it->second << endl;
        ++it;
    }
    cout << endl;
    for (auto e : m)
    {
        cout << e.first << " : " << e.second << endl;
    }
    cout << endl;
}
void testmap1()
{
    string strs[] = {"西瓜", "樱桃", "西瓜", "苹果", "西瓜", "西瓜", "西瓜", "苹果"};
    map<string, int> countMap;
    for (auto &str : strs)
    {
        map<string, int>::iterator pos = countMap.find(str);
        if (pos != countMap.end())
        {
            pos->second++;
        }
        else
        {
            countMap.insert(make_pair(str, 1));
        }
    }
    for (auto &e : countMap)
    {
        cout << e.first << " : " << e.second << endl;
    }
    cout << endl;
}
void testmap2()
{
    string strs[] = {"西瓜", "樱桃", "西瓜", "苹果", "西瓜", "西瓜", "西瓜", "苹果"};
    map<string, int> countMap;
    for (auto &str : strs)
    {
        countMap[str]++;
    }
    for (auto &e : countMap)
    {
        cout << e.first << " : " << e.second << endl;
    }
    cout << endl;
}
void testmap3()
{
    string strs[] = {"西瓜", "樱桃", "西瓜", "苹果", "西瓜", "西瓜", "西瓜", "苹果"};
    map<string, int> countMap;
    for (auto &str : strs)
    {
        pair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(str, 1));
        if (ret.second == false)
        {
            ret.first->second++;
        }
    }
    for (auto &e : countMap)
    {
        cout << e.first << " : " << e.second << endl;
    }
    cout << endl;
}
void testmap4()
{
    string strs[] = {"西瓜", "樱桃", "西瓜", "苹果", "西瓜", "西瓜", "西瓜", "苹果"};
    map<string, int> countMap;
    for (auto &str : strs)
    {
        countMap[str]++;
    }
    countMap["香蕉"];                 // 插入
    countMap["香蕉"] = 10;            // 修改
    cout << countMap["香蕉"] << endl; // 查找
    countMap["哈密瓜"] = 5;           // 插入+修改
    for (auto &e : countMap)
    {
        cout << e.first << " : " << e.second << endl;
    }
    cout << endl;
}
void testmap5()
{
    map<string, string> dict;
    dict.insert(make_pair("sort", "排序"));
    dict["string"];
    dict["string"] = "字符串";
    dict["left"] = "左边";
    for (auto &e : dict)
    {
        cout << e.first << " : " << e.second << endl;
    }
    cout << endl;
}
void testmultiset()
{
    multiset<int> ms;
    ms.insert(3);
    ms.insert(2);
    ms.insert(3);
    ms.insert(1);
    ms.insert(4);
    ms.insert(5);
    ms.insert(3);
    for (auto e : ms)
    {
        cout << e << " ";
    }
    cout << endl;
    auto pos = ms.find(3);
    cout << *pos << endl;
    ++pos;
    cout << *pos << endl;
    ++pos;
    cout << *pos << endl;
}
void testmultimap()
{
    multimap<string, int> mm;
    mm.insert(make_pair("苹果", 1));
    mm.insert(make_pair("苹果", 1));
    mm.insert(make_pair("苹果", 3));
    mm.insert(make_pair("西瓜", 2));
    mm.insert(make_pair("西瓜", 1));
    for (auto e : mm)
    {
        cout << e.first << " : " << e.second << endl;
    }
    cout << endl;
}
int main()
{
    // testset();
    // testset1();
    // testmap();
    // testmap1();
    // testmap2();
    // testmap3();
    // testmap4();
    // testmap5();
    // testmultiset();
    testmultimap();
    return 0;
}